package com.platform.modules.alg.alglib.poj3067;

import java.util.Arrays;

public class Poj3067 {
    private int maxn = 1010;
    private int maxk = 1000010;

    int c[] = new int[maxn];
    int n;
    int m;
    int k;
    Edge e[] = new Edge[maxk];

    public Poj3067() {
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }

    public String output = "";

    // c[i]的区间长度
    int lowbit(int i) {
        return (-i) & i;
    }

    public String cal(String input) {
        String[] line = input.split("\n");

        String[] num = line[0].split(" ");
        n = Integer.parseInt(num[0]);
        m = Integer.parseInt(num[1]);
        k = Integer.parseInt(num[2]);

        for (int i = 0; i < k; i++) {
            String[] connect = line[i + 1].split(" ");
            e[i].x = Integer.parseInt(connect[0]);
            e[i].y = Integer.parseInt(connect[1]);
        }
        Arrays.sort(e, 0, k);

        int ans = 0;
        for (int i = 0; i < k; i++) {
            ans += i - sum(e[i].y);
            add(e[i].y);
        }
        output = ans + "";
        return output;
    }

    void add(int i) // 加 1 操作，参数省略
    {
        while (i <= m) // y 点 有 m 个
        {
            ++c[i];
            i += lowbit(i);
        }
    }

    int sum(int i) {
        int s = 0;
        while (i > 0) {
            s += c[i];
            i -= lowbit(i);
        }
        return s;
    }
}

class Edge implements Comparable<Edge> {
    int x, y;
    @Override
    public int compareTo(Edge o) {
        if (o.x == this.x) return this.y < o.y ? -1 : 1;
        return this.x < o.x ? -1 : 1;
    }
}
